package com.yoshino.leetcode.oneHundred.threetyth;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] printNumbers2(int n) {
        int m = (int) (Math.pow(10, n) - 1);
        int res[] = new int[m];
        for (int i = 0; i < m; i++) {
            res[i] = i + 1;
        }
        return res;
    }

    List<String> ans = new ArrayList<>();
    public List<String> printNumbers(int n) {
        StringBuilder sb = new StringBuilder();
        for(int i = 1;i <= n; ++i){//总位数
            for(char j = '1'; j <='9'; ++j){
                sb.append(j);
                dfs(i, 1, sb);
                sb.deleteCharAt(sb.length()-1);
            }
        }
        return ans;
    }

    private void dfs(int len, int idx, StringBuilder sb){
        if(idx == len){
            ans.add(sb.toString());
            return;
        }

        for(char j = '0'; j <='9'; ++j){
            sb.append(j);
            dfs(len, idx+1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    /**
     * 逆序列，归并排序
     * @param nums
     * @return
     */
    public int reversePairs(int[] nums) {
        int n = nums.length;

        if (n < 2) {
            return 0;
        }

        int[] temp = new int[n];

        return reversePairs(nums, 0, n - 1, temp);
    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        // 简化流程，不用排序
        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int countPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + countPairs + rightPairs;

    }

    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int ti = left;
        int tj = mid + 1;
        int count = 0;
        for (int i = left; i <= right ; i++) {
            if (tj == right + 1) {
                // 左部分已经排序完
                nums[i] = temp[ti];
                ti++;
            } else if (ti == mid + 1) {
                nums[i] = temp[tj];
                tj++;
            } else if (temp[ti] <= temp[tj]) {
                nums[i] = temp[ti];
                ti++;
            } else {
                nums[i] = temp[tj];
                tj++;
                // 3 4 | 1 2  -> 1 被排序 3 4 | 2
                count += (mid - ti + 1);
            }
        }
        return count;
    }
}